如何灵活运用递归？¶

约 491 个字 160 行代码预计阅读时间 4 分钟

100. 相同的树 ¶

判断两个节点是否同时为空
判断两个节点是否只有一个为空
判断两个节点的值是否相同
两个节点同时递归。

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None and q is None:
            return True
        if (p is None and q) or  (q is None and p):
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

101. 对称二叉树 ¶

递归的时候：一个向左，一个向右

return dfs(l.right,r.left) and dfs(l.left,r.right)

110. 平衡二叉树 ¶

如果不符合平衡二叉树，记录下，提前退出。

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(node) -> int:
            if node is None:
                return 0

            l = dfs(node.left)
            if l == -1:
                return -1
            r = dfs(node.right)
            if r == -1:
                return -1

            if abs(l - r) > 1:
                return -1
            return max(l,r) + 1
        return dfs(root) != -1

199. 二叉树的右视图 ¶

记录每一层从右边看到的第一个。

用全局变量 ans 记录答案，满足条件的加入。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(node, height):
            if node is None:
                return 
            nonlocal res
            if height == len(res):
                res.append(node.val)
            dfs(node.right, height + 1)
            dfs(node.left, height + 1)
        dfs(root,0)
        return res

965. 单值二叉树 ¶

和 100 题一样的练习题

951. 翻转等价二叉树 ¶

选择反转，或者不翻转。

在 dp 的时候也是这样，把所有的情况都枚举到，然后记忆化 + 空间优化。

class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if root1 is None and root2 is None:
            return True
        if (root1 is None and root2) or (root2 is None and root1):
            return False
        if root1.val != root2.val:
            return False
        # 不翻转
        if self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right):
            return True
        # 反转
        return self.flipEquiv(root1.left,root2.right) and self.flipEquiv(root1.right,root2.left)

617. 合并二叉树 ¶

在两个节点都不为空时，把新节点的 val，left 和 right 直接保存到 root1 中。

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right,root2.right)
        return root1

2331. 计算布尔二叉树的值 ¶

判断节点是否为叶子结点，然后递归。

508. 出现次数最多的子树元素和 ¶

Counter 记录子树元素和。

1026. 节点与其祖先之间的最大差值 ¶

从当节点来看，最大差值无非有两种情况，与子树中的最小值、最大值的差。

如果我们求的是以当前节点为根的树，它的最小值和最大值。

虽然题目要求「不同节点」，但是相同节点的差值为 0，不会影响最大差值
假设子树的最小值为 mn，最大值为 mx
max(res,abs(mx - node.val)) = max(res, abs(mx - node.val), abs(node.val - node,val))
因为 res 本身就就是大于零的，加一个0️⃣没有任何影响。

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        # 记录子树中的最大值和最小值
        res = 0
        def dfs(node)  -> (int,int):
            if node is None:
                return inf,-inf

            nonlocal res
            ln,lx = dfs(node.left)
            rn,rx = dfs(node.right)
            mn = min(node.val, ln, rn)
            mx = max(node.val, lx, rx)
            res = max(res, abs(mn - node.val), abs(mx - node.val))
            return mn,mx
        dfs(root)
        return res

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node, mn, mx):
            if node is None:
                return

            mn = min(mn, node.val)
            mx = max(mn, node,val)
            nonlocal ans
            ans = max(ans, abs(node.val - mn), abs(node.val - mx))
            dfs(node.left, mn, mx)
            dfs(node.right, mn, mx)
        dfs(root, root.val, root.val)
        return ans

只计算子树的最大值和最小值：

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(u):
            nonlocal ans
            mx, mn = u.val, u.val
            if u.left:
                lmx, lmn = dfs(u.left)
                ans = max(ans, abs(lmn - u.val), abs(u.val - lmx))
                mx = max(mx, lmx)
                mn = min(mn, lmn)
            if u.right:
                rmx, rmn = dfs(u.right)
                ans = max(ans, abs(rmn - u.val), abs(u.val - rmx))
                mx = max(mx, rmx)
                mn = min(mn, rmn)
            return mx, mn
        dfs(root)
        return ans

1372. 二叉树中的最长交错路径

记录上次的方向，和当前深度。

class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(node, is_left, dep):
            if node is None:
                return
            nonlocal res
            res = max(res, dep)
            if is_left:
                dfs(node.right, False, dep + 1)
                dfs(node.left, True, 1)
            else:
                dfs(node.left, True, dep + 1)
                dfs(node.right, False, 1)
        dfs(root.left, True, 1)
        dfs(root.right, False, 1)
        return res

1372. 二叉树中的最长交错路径 ¶

class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(node, is_left, dep):
            if node is None:
                return
            nonlocal res
            res = max(res, dep)
            if is_left:
                dfs(node.right, False, dep + 1)
                dfs(node.left, True, 1)
            else:
                dfs(node.left, True, dep + 1)
                dfs(node.right, False, 1)
        dfs(root.left, True, 1)
        dfs(root.right, False, 1)
        return res

1080. 根到叶路径上的不足节点 ¶

class Solution:
    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
        limit -= root.val
        if not (root.left or root.right):
            return None if limit > 0 else root

        if root.left:
            root.left  = self.sufficientSubset(root.left, limit)
        if root.right:
            root.right = self.sufficientSubset(root.right, limit)
        return root if root.left or root.right else None

Reference¶

如何灵活运用递归？【基础算法精讲 10】

Last update: March 19, 2025
Created: March 19, 2025

如何灵活运用递归？¶

Reference¶

Comments